package ali;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *
 * 144. 二叉树的前序遍历
 * https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
 * @author wxh
 */
public class Solution_3 {

	//解法1：递归实现
	public List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}
		preOrder(root, list);
		return list;
	}

	public void preOrder(TreeNode treeNode,List<Integer> list) {
		if (treeNode == null) {
			return;
		}
		list.add(treeNode.val);
		preOrder(treeNode.left, list);
		preOrder(treeNode.right, list);
	}

	//解法2：借助栈，迭代法实现
	public List<Integer> preorderTraversal2(TreeNode root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) {
			return list;
		}

		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode curNode = root;
		while (curNode != null || !stack.empty()) {
			if (curNode != null) {
				list.add(curNode.val);
				stack.push(curNode);
				curNode = curNode.left;
			} else {
				curNode = stack.pop().right;
			}
		}
		return list;
	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

}